{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Volume of Histogram LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #two-pointers #dynamic-programming #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #双指针 #动态规划 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #直方图的水量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png\" style=\"height: 161px; width: 412px;\"></p>\n",
    "\n",
    "<p><small>上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。&nbsp;<strong>感谢 Marcos</strong> 贡献此图。</small></p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> [0,1,0,2,1,0,1,3,2,1,2,1]\n",
    "<strong>输出:</strong> 6</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [volume-of-histogram-lcci](https://leetcode.cn/problems/volume-of-histogram-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [volume-of-histogram-lcci](https://leetcode.cn/problems/volume-of-histogram-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if height==[]:\n",
    "            return 0\n",
    "        max_height = max(height)\n",
    "        left_max_index,right_max_index = 0,len(height)-1\n",
    "        # cur_max_height = 1\n",
    "        answer = -sum(height)\n",
    "        for i in range(1,max_height+1):\n",
    "            while(left_max_index<=right_max_index and height[left_max_index]<i):\n",
    "                left_max_index += 1\n",
    "            while(left_max_index<=right_max_index and height[right_max_index]<i):\n",
    "                right_max_index -= 1\n",
    "            answer += right_max_index-left_max_index+1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if height==[]:\n",
    "            return 0\n",
    "        max_height = max(height)\n",
    "        left_max_index,right_max_index = 0,len(height)-1\n",
    "        # cur_max_height = 1\n",
    "        answer = -sum(height)\n",
    "        for i in range(1,max_height+1):\n",
    "            while(left_max_index<=right_max_index and height[left_max_index]<i):\n",
    "                left_max_index += 1\n",
    "            while(left_max_index<=right_max_index and height[right_max_index]<i):\n",
    "                right_max_index -= 1\n",
    "            answer += right_max_index-left_max_index+1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if height==[]:\n",
    "            return 0\n",
    "        max_height = max(height)\n",
    "        left_max_index,right_max_index = 0,len(height)-1\n",
    "        # cur_max_height = 1\n",
    "        answer = -sum(height)\n",
    "        for i in range(1,max_height+1):\n",
    "            while(left_max_index<=right_max_index and height[left_max_index]<i):\n",
    "                left_max_index += 1\n",
    "            while(left_max_index<=right_max_index and height[right_max_index]<i):\n",
    "                right_max_index -= 1\n",
    "            answer += right_max_index-left_max_index+1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n= len(height)\n",
    "        l,r = 0,n-1\n",
    "        leftmax,rightmax=0,0\n",
    "        rt = 0\n",
    "        while l<r:\n",
    "            if height[l]<height[r]:\n",
    "                leftmax = max(leftmax,height[l])\n",
    "                rt+=(leftmax-height[l])\n",
    "                l+=1\n",
    "            else:\n",
    "                rightmax = max(rightmax,height[r])\n",
    "                rt+=(rightmax-height[r])\n",
    "                r-=1\n",
    "        return rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if height==[]:\n",
    "            return 0\n",
    "        max_height = max(height)\n",
    "        left_max_index,right_max_index = 0,len(height)-1\n",
    "        # cur_max_height = 1\n",
    "        answer = -sum(height)\n",
    "        for i in range(1,max_height+1):\n",
    "            while(left_max_index<=right_max_index and height[left_max_index]<i):\n",
    "                left_max_index += 1\n",
    "            while(left_max_index<=right_max_index and height[right_max_index]<i):\n",
    "                right_max_index -= 1\n",
    "            answer += right_max_index-left_max_index+1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "from typing import List\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        queue = Queue()\n",
    "        left = [0] * n\n",
    "        for i in range(n):\n",
    "            while not queue.empty() and height[i] > height[queue.queue[0]]:\n",
    "                queue.get(0)\n",
    "            if queue.empty():\n",
    "                queue.put(i)\n",
    "                left[i] = -1\n",
    "            else:\n",
    "                left[i] = queue.queue[0]\n",
    "\n",
    "        right = [0]* n\n",
    "        while not queue.empty():\n",
    "            queue.get()\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            while not queue.empty() and height[i] > height[queue.queue[0]]:\n",
    "                queue.get(0)\n",
    "            if queue.empty():\n",
    "                queue.put(i)\n",
    "                right[i] = -1\n",
    "            else:\n",
    "                 right[i] = queue.queue[0]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(0,n):\n",
    "            if not left[i] == -1 and  not right[i] == -1:\n",
    "                ans += min(height[left[i]],height[right[i]]) - height[i]\n",
    "\n",
    "        return ans;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans=0\n",
    "        left,right=0,len(height)-1\n",
    "        leftMax=rightMax=0\n",
    "        while left<right:\n",
    "            leftMax=max(leftMax,height[left])\n",
    "            rightMax=max(rightMax,height[right])\n",
    "            if height[left]<height[right]:\n",
    "                ans+=leftMax-height[left]\n",
    "                left+=1\n",
    "            else:\n",
    "                ans+=rightMax-height[right]\n",
    "                right-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, s: List[int]) -> int:\n",
    "        stack=[]\n",
    "        ans = 0\n",
    "        for i,h in enumerate(s):\n",
    "            while stack and h>s[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "\n",
    "                left = stack[-1]\n",
    "                width = i-left-1\n",
    "                height = min(s[i],s[left])-s[top]\n",
    "                ans = ans+ width*height\n",
    "            \n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if not height:\n",
    "            return 0\n",
    "        zhuzi = sum(height)\n",
    "        length = 1 # 表示第几层\n",
    "        res = 0\n",
    "        while length<=max(height):\n",
    "            left = 0\n",
    "            right = len(height)-1\n",
    "            while height[left]<length:\n",
    "                left+=1\n",
    "            while height[right]<length:\n",
    "                right-=1\n",
    "            res += right-left+1\n",
    "            length+=1\n",
    "        return res-zhuzi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        Sum = sum(height)\n",
    "        size = len(height)\n",
    "        left, right = 0, size - 1\n",
    "        volume, high = 0, 1\n",
    "        while left <= right:\n",
    "            while left <= right and height[left] < high:\n",
    "                left += 1\n",
    "            while left <= right and height[right] < high:\n",
    "                right -= 1\n",
    "            high += 1\n",
    "            volume += right - left + 1\n",
    "        return volume - Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height):\n",
    "        stack, ret = [], 0\n",
    "        for i, h in enumerate(height):\n",
    "            while stack and height[stack[-1]] < h:\n",
    "                top = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                left = stack[-1]\n",
    "                ret += (i - left - 1) * (min(height[left], h) - height[top])\n",
    "            stack.append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(height) - 1):\n",
    "            left_height = max(height[0: i])\n",
    "            right_height = max(height[i + 1:])\n",
    "            min_height = min(left_height, right_height)\n",
    "            if min_height > height[i]:\n",
    "                res += min_height - height[i]\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if height==[]:\n",
    "            return 0\n",
    "        max_height = max(height)\n",
    "        left_max_index,right_max_index = 0,len(height)-1\n",
    "        # cur_max_height = 1\n",
    "        answer = -sum(height)\n",
    "        for i in range(1,max_height+1):\n",
    "            while(left_max_index<=right_max_index and height[left_max_index]<i):\n",
    "                left_max_index += 1\n",
    "            while(left_max_index<=right_max_index and height[right_max_index]<i):\n",
    "                right_max_index -= 1\n",
    "            answer += right_max_index-left_max_index+1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        \n",
    "        left_max, right_max = 0, 0\n",
    "        while left < right:\n",
    "            left_max = max(left_max, height[left])\n",
    "            right_max = max(right_max, height[right])\n",
    "\n",
    "            if height[left] < height[right]:\n",
    "                ans += left_max - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += right_max - height[right]\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        Sum = sum(height) # 得到柱子的体积\n",
    "        size = len(height) \n",
    "        left, right = 0, size - 1 # 双指针初始化\n",
    "        volume, high = 0, 1 # 总体积和高度初始化\n",
    "        while (left <= right):\n",
    "            while (left <= right and height[left] < high): \n",
    "                left += 1 \n",
    "            while (left <= right and height[right] < high):\n",
    "                right -= 1\n",
    "            volume += right - left + 1 # 每一层的容量都加起来\n",
    "            high += 1 # 高度加一\n",
    "        return volume - Sum # 总体积减去柱子体积，即雨水总量\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        leftMax = rightMax = 0\n",
    "\n",
    "        while left < right:\n",
    "            leftMax = max(leftMax, height[left])\n",
    "            rightMax = max(rightMax, height[right])\n",
    "            if height[left] < height[right]:\n",
    "                ans += leftMax - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += rightMax - height[right]\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        leftMax = rightMax = 0\n",
    "\n",
    "        while left < right:\n",
    "            leftMax = max(leftMax, height[left])\n",
    "            rightMax = max(rightMax, height[right])\n",
    "            if height[left] < height[right]:\n",
    "                ans += leftMax - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += rightMax - height[right]\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "       \n",
    "\n",
    "        n = len(height)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        l = 1\n",
    "        r = n - 2\n",
    "        leftMax = height[0]\n",
    "        rightMax = height[n - 1]\n",
    "        ans = 0\n",
    "\n",
    "        while l <= r:\n",
    "            if leftMax <= rightMax:\n",
    "                if leftMax < height[l]:\n",
    "                    leftMax = height[l]\n",
    "                else:\n",
    "                 ans += leftMax - height[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                if rightMax < height[r]:\n",
    "                    rightMax = height[r]\n",
    "                else:\n",
    "                    ans += rightMax - height[r]\n",
    "                r -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n=len(height)\n",
    "        ans=0\n",
    "        stack=[]\n",
    "        for i in range(n):\n",
    "            if stack and height[stack[-1]]==height[i]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            while stack and height[stack[-1]]<height[i]:\n",
    "                mid=height[stack.pop()]\n",
    "                if stack:\n",
    "                    h=min(height[i],height[stack[-1]])-mid\n",
    "                    w=i-stack[-1]-1\n",
    "                    ans+=w*h\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        leftMax = rightMax = 0\n",
    "\n",
    "        while left < right:\n",
    "            leftMax = max(leftMax, height[left])\n",
    "            rightMax = max(rightMax, height[right])\n",
    "            if height[left] < height[right]:\n",
    "                ans += leftMax - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += rightMax - height[right]\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if not height:\n",
    "            return 0\n",
    "\n",
    "        n = len(height)\n",
    "        dp_left = [0 for _ in range(n)]\n",
    "        dp_right = [0 for _ in range(n)]\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp_left[i] = max(dp_left[i-1], height[i-1])\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp_right[i] = max(dp_right[i+1], height[i+1])\n",
    "            short = min(dp_left[i], dp_right[i])\n",
    "            if short > height[i]:\n",
    "                res += (short - height[i])\n",
    "\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     short = min(dp_left[i], dp_right[i])\n",
    "        #     if short > dictionary[i]:\n",
    "        #         res += (short - dictionary[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if not len(height):\n",
    "            return 0\n",
    "\n",
    "\n",
    "        n = len(height)\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        total = 0\n",
    "        min_height = 0\n",
    "        while i < j:\n",
    "            if height[i] < height[j]:\n",
    "                total += (height[i] - min_height) * (j - i + 1)\n",
    "                min_height = height[i]\n",
    "                while i < j and height[i] <= min_height:\n",
    "                    i += 1\n",
    "                \n",
    "            elif height[i] == height[j]:\n",
    "                total += (height[i] - min_height) * (j - i + 1)\n",
    "                min_height = height[i]\n",
    "                while i < j and height[i] <= min_height:\n",
    "                    i += 1\n",
    "                \n",
    "                while j > i and height[j] <= min_height:\n",
    "                    j -= 1\n",
    "            \n",
    "            else:\n",
    "                total += (height[j] - min_height) * (j - i + 1)\n",
    "                min_height = height[j]\n",
    "                while j > i and height[j] <= min_height:\n",
    "                    j -= 1\n",
    "        \n",
    "\n",
    "        total += height[i] - min_height #### 突出的部分\n",
    "        \n",
    "        return total - sum(height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "       \n",
    "\n",
    "        n = len(height)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        l = 1\n",
    "        r = n - 2\n",
    "        leftMax = height[0]\n",
    "        rightMax = height[n - 1]\n",
    "        ans = 0\n",
    "\n",
    "        while l <= r:\n",
    "            if leftMax <= rightMax:\n",
    "                if leftMax < height[l]:\n",
    "                    leftMax = height[l]\n",
    "                else:\n",
    "                 ans += leftMax - height[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                if rightMax < height[r]:\n",
    "                    rightMax = height[r]\n",
    "                else:\n",
    "                    ans += rightMax - height[r]\n",
    "                r -= 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for i in range(len(height)):\n",
    "            while st and height[i] >= st[-1][0]:\n",
    "               a,b = st.pop()\n",
    "               if not st:\n",
    "                   break\n",
    "               ans += (min(height[i], st[-1][0]) - a) * (i-st[-1][1] - 1)\n",
    "            st.append((height[i], i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        l, r = 0, n - 1\n",
    "        level = 1\n",
    "        total = 0\n",
    "        while l <= r:\n",
    "            while l <= r and height[l] < level:\n",
    "                l += 1\n",
    "            while l <= r and height[r] < level:\n",
    "                r -= 1\n",
    "            total += r - l + 1\n",
    "            level += 1\n",
    "        return total - sum(height)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        stack = []\n",
    "        area = 0\n",
    "        for i in range(n):\n",
    "            while stack and height[i] > height[stack[-1]]:\n",
    "                index = stack.pop()\n",
    "                if stack:\n",
    "                    h = min(height[i], height[stack[-1]]) - height[index]\n",
    "                    w = i - stack[-1] - 1\n",
    "                    area += h * w\n",
    "            stack.append(i)\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        for i in range(1, n):\n",
    "            left[i] = max(left[i - 1], height[i - 1])\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = max(right[i + 1], height[i + 1])\n",
    "        volume = 0\n",
    "        for i in range(n):\n",
    "            volume += max(min(left[i], right[i]) - height[i], 0)\n",
    "        return volume"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        stack = list()\n",
    "        n = len(height)\n",
    "        \n",
    "        for i, h in enumerate(height):\n",
    "            while stack and h > height[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                left = stack[-1]\n",
    "                currWidth = i - left - 1\n",
    "                currHeight = min(height[left], height[i]) - height[top]\n",
    "                ans += currWidth * currHeight\n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        L = len(height) \n",
    "        if L <= 2:\n",
    "            return 0 \n",
    "\n",
    "        left = [0 for _ in range(L)]\n",
    "        right = [0 for _ in range(L)]\n",
    "\n",
    "        left[0] = height[0]\n",
    "        for idx in range(1, L): \n",
    "            left[idx] = max(left[idx - 1], height[idx])\n",
    "\n",
    "        right[-1] = height[-1]\n",
    "        for idx in range(L - 2, -1, -1):\n",
    "            right[idx] = max(right[idx + 1], height[idx])\n",
    "\n",
    "        res = 0 \n",
    "        for idx in range(1, L - 1): \n",
    "            bound = min(left[idx - 1], right[idx + 1])\n",
    "            if bound > height[idx]:\n",
    "                res += bound - height[idx]\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        \n",
    "        left_max, right_max = 0, 0\n",
    "        while left < right:\n",
    "            left_max = max(left_max, height[left])\n",
    "            right_max = max(right_max, height[right])\n",
    "\n",
    "            if height[left] < height[right]:\n",
    "                ans += left_max - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += right_max - height[right]\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        stack = [0]\n",
    "        res = 0\n",
    "        for i in range(1, len(height)):\n",
    "            if height[i] < height[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            elif height[i] == height[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and height[stack[-1]] < height[i]:\n",
    "                    mid = stack.pop()\n",
    "                    if stack:\n",
    "                        l = stack[-1]\n",
    "                        r = i \n",
    "                        h = min(height[l], height[r]) - height[mid]\n",
    "                        w = r-l-1\n",
    "                        res += h*w\n",
    "\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        stack = list()\n",
    "        n = len(height)\n",
    "        \n",
    "        for i, h in enumerate(height):\n",
    "            while stack and h > height[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                left = stack[-1]\n",
    "                currWidth = i - left - 1\n",
    "                currHeight = min(height[left], height[i]) - height[top]\n",
    "                ans += currWidth * currHeight\n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        leftMax = rightMax = 0\n",
    "\n",
    "        while left < right:\n",
    "            leftMax = max(leftMax, height[left])\n",
    "            rightMax = max(rightMax, height[right])\n",
    "            if height[left] < height[right]:\n",
    "                ans += leftMax - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += rightMax - height[right]\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        # 前、后最小前缀数组\n",
    "        # 桶原理\n",
    "        # 先把height两边的0去掉\n",
    "        \n",
    "        # n = len(height)\n",
    "        # if n == 0:\n",
    "        #     return 0\n",
    "\n",
    "        # pre = [0]*n\n",
    "        # pre[0] = height[0]\n",
    "        # for i in range(1, n):\n",
    "        #     pre[i] = max(pre[i-1], height[i])\n",
    "        # sur = [0]*n\n",
    "        # sur[-1] = height[-1]\n",
    "        # for i in range(n-2, -1, -1):\n",
    "        #     sur[i] = max(sur[i+1], height[i])\n",
    "        # print(pre, sur)\n",
    "\n",
    "        # sum_ = 0\n",
    "        # for i in range(n):\n",
    "        #     sum_ += (min(pre[i], sur[i])*1-height[i])\n",
    "        # return sum_\n",
    "\n",
    "\n",
    "        # 栈--有点难想到啊，上面的更好理解\n",
    "        stack, ret = [], 0\n",
    "        for i, h in enumerate(height):\n",
    "            while stack and height[stack[-1]] < h:\n",
    "                top = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                left = stack[-1]\n",
    "                ret += (i - left - 1) * (min(height[left], h) - height[top])\n",
    "            stack.append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        stack,ans=[],0\n",
    "        for i,h in enumerate(height):\n",
    "            while stack and h>height[stack[-1]]:\n",
    "                bottom=height[stack.pop()]\n",
    "                if stack:\n",
    "                    ans+=(min(h,height[stack[-1]])-bottom)*(i-stack[-1]-1)\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        Sum = sum(height) # 得到柱子的体积\n",
    "        size = len(height) \n",
    "        left, right = 0, size - 1 # 双指针初始化\n",
    "        volume, high = 0, 1 # 总体积和高度初始化\n",
    "        while (left <= right):\n",
    "            while (left <= right and height[left] < high): \n",
    "                left += 1 \n",
    "            while (left <= right and height[right] < high):\n",
    "                right -= 1\n",
    "            volume += right - left + 1 # 每一层的容量都加起来\n",
    "            high += 1 # 高度加一\n",
    "        return volume - Sum # 总体积减去柱子体积，即雨水总量\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "      stack = []\n",
    "      rain = 0\n",
    "      for i in range(len(height)):\n",
    "        while stack and height[stack[-1]]<=height[i]:\n",
    "          mid = stack.pop()\n",
    "          if not stack:\n",
    "            break\n",
    "          h = min(height[stack[-1]],height[i])-height[mid]\n",
    "          w = i - stack[-1]-1\n",
    "          area = h*w\n",
    "          rain = rain + area\n",
    "        stack.append(i)\n",
    "      return rain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n, res = len(height), 0\n",
    "        if n <= 2: return 0\n",
    "        l_max, r_max = height[0], height[-1]\n",
    "        l, r = 1, n - 2\n",
    "        while l <= r:\n",
    "            if l_max < r_max:\n",
    "                res += max(l_max - height[l], 0)\n",
    "                l_max = max(l_max, height[l])\n",
    "                l += 1\n",
    "            else:\n",
    "                res += max(r_max - height[r], 0)\n",
    "                r_max = max(r_max, height[r])\n",
    "                r -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        left, right = 0, n - 1\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            \n",
    "            left = max(height[0:i])\n",
    "            right = max(height[i + 1: n])      \n",
    "            if left >= height[i] and right >= height[i]:\n",
    "                res += min(left, right) - height[i]\n",
    "                \n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left,right = 0, len(height)-1\n",
    "        leftMax = rightMax = 0\n",
    "\n",
    "        while left < right:\n",
    "            leftMax = max(leftMax, height[left])\n",
    "            rightMax = max(rightMax,height[right])\n",
    "            if height[left] < height[right]:\n",
    "                ans += leftMax - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += rightMax - height[right]\n",
    "                right -= 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ac=0;ba=len(height)-1;watersum=0;\n",
    "        maxac=0;maxba=0;\n",
    "        while ac<ba:\n",
    "            maxac=max(maxac,height[ac])\n",
    "            maxba=max(maxba,height[ba])\n",
    "            if maxac<maxba:\n",
    "                watersum+=maxac-height[ac]\n",
    "                ac+=1\n",
    "            else:\n",
    "                watersum+=maxba-height[ba]\n",
    "                ba-=1\n",
    "        return watersum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        l = 0\n",
    "        r = n - 1 \n",
    "        res = 0\n",
    "        maxL = 0\n",
    "        maxR = 0\n",
    "        while l < r:\n",
    "            if height[l] < height[r]:\n",
    "                maxL = max(maxL, height[l])\n",
    "                res += maxL - height[l]\n",
    "                l += 1 \n",
    "            else:\n",
    "                maxR = max(maxR, height[r])\n",
    "                res += maxR - height[r]\n",
    "                r -= 1 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height) -> int:\n",
    "        Sum = sum(height) # 得到柱子的体积\n",
    "        size = len(height) \n",
    "        left, right = 0, size - 1 # 双指针初始化\n",
    "        volume, high = 0, 1 # 总体积和高度初始化\n",
    "        while (left <= right):\n",
    "            while (left <= right and height[left] < high): \n",
    "                left += 1 \n",
    "            while (left <= right and height[right] < high):\n",
    "                right -= 1\n",
    "            volume += right - left + 1 # 每一层的容量都加起来\n",
    "            high += 1 # 高度加一\n",
    "        return volume - Sum # 总体积减去柱子体积，即雨水总量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if not height:\n",
    "            return 0\n",
    "        \n",
    "        n = len(height)\n",
    "        leftMax = [height[0]] + [0] * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            leftMax[i] = max(leftMax[i - 1], height[i])\n",
    "\n",
    "        rightMax = [0] * (n - 1) + [height[n - 1]]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            rightMax[i] = max(rightMax[i + 1], height[i])\n",
    "\n",
    "        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        stack = list()\n",
    "        n = len(height)\n",
    "        \n",
    "        for i, h in enumerate(height):\n",
    "            while stack and h > height[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                left = stack[-1]\n",
    "                currWidth = i - left - 1\n",
    "                currHeight = min(height[left], height[i]) - height[top]\n",
    "                ans += currWidth * currHeight\n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ans = 0\n",
    "        left, right = 0, len(height) - 1\n",
    "        leftMax = rightMax = 0\n",
    "\n",
    "        while left < right:\n",
    "            leftMax = max(leftMax, height[left])\n",
    "            rightMax = max(rightMax, height[right])\n",
    "            if height[left] < height[right]:\n",
    "                ans += leftMax - height[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans += rightMax - height[right]\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        len_height = len(height)\n",
    "        if len_height < 3:\n",
    "            return 0\n",
    "        left_gt = [0] * len_height\n",
    "        right_gt = [0] * len_height\n",
    "        left_max = height[0]\n",
    "        for i in range(1, len_height):\n",
    "            if height[i] < left_max:\n",
    "                left_gt[i] = left_max\n",
    "            else:\n",
    "                left_max = height[i]\n",
    "        right_max = height[-1]\n",
    "        for i in reversed(range(len_height - 1)):\n",
    "            if height[i] < right_max:\n",
    "                right_gt[i] = right_max\n",
    "            else:\n",
    "                right_max = height[i]\n",
    "        rst = 0\n",
    "        return sum(max(min(left, right) - hght, 0) for left, right, hght in zip(left_gt, right_gt, height))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        res = 0\n",
    "        stack = [0]\n",
    "        for i in range(1, len(height)):\n",
    "            if height[i] < height[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            elif height[i] == height[stack[-1]]:\n",
    "                stack[-1] = i \n",
    "            else:\n",
    "                while stack and height[i] > height[stack[-1]]:\n",
    "                    mid = stack.pop()\n",
    "                    if stack:\n",
    "                        l = stack[-1]\n",
    "                        r = i \n",
    "                        w = r-l-1\n",
    "                        h = min(height[l], height[r]) - height[mid]\n",
    "                        res += w*h \n",
    "                stack.append(i)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "# # 首先寻找整个高度图中最高的作为“坑”的一个边界，记住它的位置，有多个相同的最高度取最后一个记录的就ok，对结果没影响。\n",
    "# # 然后从左向最高点所在位置遍历，记录当前点左侧的最高点高度，若当前点高度比左边的最高点高度低，说明当前点处于左侧最高点和全图最高点之间的“坑”内，蓄水高度 = 左侧最高点-当前点高度（木桶理论嘛，蓄水量由最低板决定）。 若当前点比左侧最高点更高，我们更新高度，当然，当前点也蓄不了水。\n",
    "# # 同理，再从右侧向最高点所在位置遍历。\n",
    "#         maxHPos = 0\n",
    "#         maxH = 0\n",
    "#         res = 0\n",
    "#         for i in range(len(height)):\n",
    "#             if height[i] > maxH:\n",
    "#                 maxHPos = i;\n",
    "#                 maxH = height[i];\n",
    "#         maxH = 0\n",
    "#         for i in range(maxHPos):\n",
    "#             if height[i] >= maxH:\n",
    "#                 maxH = height[i]\n",
    "#             else:\n",
    "#                 res += maxH - height[i]\n",
    "#         maxH = 0\n",
    "#         for i in range(len(height) - 1, maxHPos, -1):\n",
    "#             if height[i] >= maxH:\n",
    "#                 maxH = height[i]\n",
    "#             else:\n",
    "#                 res += maxH - height[i]\n",
    "#         return res\n",
    "\n",
    "        # #动态规划\n",
    "        # if not height:\n",
    "        #     return 0\n",
    "        # n = len(height)\n",
    "        # leftMax = [height[0]] + [0] * (n - 1)\n",
    "        # for i in range(1, n):\n",
    "        #     leftMax[i] = max(leftMax[i - 1], height[i])\n",
    "        # rightMax = [0] * (n - 1) + [height[n - 1]]\n",
    "        # for i in range(n - 2, -1, -1):\n",
    "        #     rightMax[i] = max(rightMax[i + 1], height[i])\n",
    "        # ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))\n",
    "        # return ans\n",
    "\n",
    "        # #双指针，优化动态规划\n",
    "        # ans = 0\n",
    "        # left, right = 0, len(height) - 1\n",
    "        # leftMax = rightMax = 0\n",
    "        # while left < right:\n",
    "        #     leftMax = max(leftMax, height[left])\n",
    "        #     rightMax = max(rightMax, height[right])\n",
    "        #     if height[left] < height[right]:\n",
    "        # # 为什么可以直接得出iLeftMax < jRightMax？\n",
    "        # # 首先，我们定义了当height[i]小于height[j]去，我们就去向右移动i，j不动\n",
    "        # # 我们不妨假设iLeftMax大于jRightMax，那么i肯定不会移动，一直卡在iLeftMax的那个i点，不会出现height[i] < height[j]\n",
    "        # # 所以如果出现了height[i] < height[j]，那么肯定是这个过程中，i左边的最大值有出现过比j右边最大值小的情况，i才会移动\n",
    "        #         ans += leftMax - height[left]\n",
    "        #         left += 1\n",
    "        #     else:\n",
    "        #         ans += rightMax - height[right]\n",
    "        #         right -= 1\n",
    "        # return ans\n",
    "\n",
    "        #栈\n",
    "        ans = 0\n",
    "        stack = list()\n",
    "        n = len(height)\n",
    "        for i, h in enumerate(height):\n",
    "            while stack and h > height[stack[-1]]:\n",
    "                top = stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                left = stack[-1]\n",
    "                currWidth = i - left - 1\n",
    "                currHeight = min(height[left], height[i]) - height[top]\n",
    "                ans += currWidth * currHeight\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n, res = len(height), 0\n",
    "        l_max, r_max = [0] * n, [0] * n\n",
    "        for i in range(1, n - 1):\n",
    "            l_max[i] = max(height[i - 1], l_max[i - 1])\n",
    "            r_max[-(i + 1)] = max(height[-i], r_max[-i])\n",
    "        for i in range(1, n - 1):\n",
    "            res += max(min(l_max[i], r_max[i]) - height[i], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def trap(self, height: List[int]) -> int:\r\n",
    "        n = len(height)\r\n",
    "        lmax, rmax = [], []\r\n",
    "\r\n",
    "        tmp = 0\r\n",
    "        for h in height:\r\n",
    "            tmp = max(tmp, h)\r\n",
    "            lmax.append(tmp)\r\n",
    "        tmp = 0\r\n",
    "        for h in reversed(height):\r\n",
    "            tmp = max(tmp, h)\r\n",
    "            rmax.insert(0, tmp)\r\n",
    "\r\n",
    "        sum = 0\r\n",
    "        for i in range(1, n - 1):\r\n",
    "            sum += max(min(lmax[i - 1], rmax[i + 1]) - height[i], 0)\r\n",
    "        return sum\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        # 接雨水：每一个位置接水量取决于左右两边的最大高度（包括自己更好写）\n",
    "        # 1、求出每个位置左边的最大值\n",
    "        lmax = [0] * len(height)\n",
    "        num = 0\n",
    "        for i in range(len(height)):\n",
    "            num = max(num, height[i])\n",
    "            lmax[i] = num\n",
    "        # 2、求出每个位置右边的最大值\n",
    "        rmax = [0] * len(height)\n",
    "        num = 0\n",
    "        for i in range(len(height) - 1, -1, -1):\n",
    "            num = max(num, height[i])\n",
    "            rmax[i] = num\n",
    "        # 3、遍历每个元素求接水量\n",
    "        result = 0\n",
    "        for i in range(len(height)):\n",
    "            ans = min(lmax[i], rmax[i]) - height[i]\n",
    "            result += ans\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if not height:return 0\n",
    "        n=len(height)\n",
    "        leftMax=[height[0]]+[0]*(n-1)\n",
    "        for i in range(1,n):\n",
    "            leftMax[i]=max(leftMax[i-1],height[i])\n",
    "        rightMax=[0]*(n-1)+[height[n-1]]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            rightMax[i]=max(rightMax[i+1],height[i])\n",
    "        ans=sum(min(leftMax[i],rightMax[i])-height[i] for i in range(n))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        stack = [0]\n",
    "        res = 0 \n",
    "        for i in range(1, len(height)):\n",
    "            if height[i] < height[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            elif height[i] == height[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and height[i] > height[stack[-1]]:\n",
    "                    mid = stack.pop()\n",
    "                    if stack:\n",
    "                        l = stack[-1]\n",
    "                        r = i \n",
    "                        h = min(height[l], height[r]) - height[mid]\n",
    "                        w = r-l - 1\n",
    "                        res += w*h \n",
    "                stack.append(i)\n",
    "                \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        if height==[]:\n",
    "            return 0\n",
    "        max_height = max(height)\n",
    "        left_max_index,right_max_index = 0,len(height)-1\n",
    "        # cur_max_height = 1\n",
    "        answer = -sum(height)\n",
    "        for i in range(1,max_height+1):\n",
    "            while(left_max_index<=right_max_index and height[left_max_index]<i):\n",
    "                left_max_index += 1\n",
    "            while(left_max_index<=right_max_index and height[right_max_index]<i):\n",
    "                right_max_index -= 1\n",
    "            print(i,right_max_index-left_max_index+1)\n",
    "            answer += right_max_index-left_max_index+1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        # 记录左右最高的\n",
    "        n = len(height)\n",
    "        l, r = [], []\n",
    "        lm = rm = 0\n",
    "        for h in height:\n",
    "            l.append(lm)\n",
    "            lm = max(lm, h)\n",
    "        for h in height[::-1]:\n",
    "            r.append(rm)\n",
    "            rm = max(rm, h)\n",
    "        r.reverse()\n",
    "        ans = 0\n",
    "        for i,h in enumerate(height):\n",
    "            ans += max(min(l[i], r[i]) - h, 0)\n",
    "        #     print(max(min(l[i], r[i]) - h, 0),end=', ')\n",
    "        # print('')\n",
    "        # print(l)\n",
    "        # print(r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        lmax, rmax = [], []\n",
    "\n",
    "        tmp = 0\n",
    "        for h in height:\n",
    "            tmp = max(tmp, h)\n",
    "            lmax.append(tmp)\n",
    "            rmax.append(0)\n",
    "        tmp = 0\n",
    "        for i in range(n, 0, -1):\n",
    "            tmp = max(tmp, height[i - 1])\n",
    "            rmax[i - 1] = tmp\n",
    "\n",
    "        sum = 0\n",
    "        for i in range(1, n - 1):\n",
    "            sum += max(min(lmax[i - 1], rmax[i + 1]) - height[i], 0)\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        if n==0:return 0\n",
    "        left,right = [0]*n,[0]*n\n",
    "        left[0],right[-1] = height[0],height[-1]\n",
    "        for i in range(1,n):\n",
    "            left[i] = max(left[i-1],height[i])\n",
    "        for i in range(n-2,-1,-1):\n",
    "            right[i] = max(right[i+1],height[i])\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            tmp = min(left[i],right[i])\n",
    "            if tmp==-1:continue\n",
    "            res+=(tmp-height[i])\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        ll = len(height)\n",
    "        r_max = [0]*ll\n",
    "        l_max = [0]*ll\n",
    "\n",
    "\n",
    "        if not height:\n",
    "            return 0\n",
    "        temp = height[0]\n",
    "        for i in range(ll-1):\n",
    "            temp = max(temp,height[i])\n",
    "            l_max[i+1] = temp\n",
    "        temp = height[ll-1]\n",
    "        for i in range(ll-1,0,-1):\n",
    "            temp = max(temp,height[i])\n",
    "            r_max[i-1] = temp\n",
    "\n",
    "\n",
    "        # for i in range(ll-1):\n",
    "        #     temp = height[i+1]\n",
    "        #     for j in range(i+1,ll):\n",
    "        #         temp = max(temp,height[j])\n",
    "        #     r_max[i] = temp\n",
    "        # for i in range(ll-1,0,-1):\n",
    "        #     temp = height[i-1]\n",
    "        #     for j in range(i-1,-1,-1):\n",
    "        #         temp = max(temp,height[j])\n",
    "        #     l_max[i] = temp\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(ll):\n",
    "            temp = min(l_max[i],r_max[i])-height[i]\n",
    "            if temp > 0:\n",
    "                res += temp\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n=len(height)\n",
    "        ans=0\n",
    "        lmax,rmax=height.copy(),height.copy()\n",
    "        for i in range(1,n):lmax[i]=max(height[i],lmax[i-1])\n",
    "        for i in range(n-2,-1,-1):rmax[i]=max(height[i],rmax[i+1])\n",
    "        for i in range(n):\n",
    "            ans+=min(lmax[i],rmax[i])-height[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "可以使用贡献法\n",
    "某个坑能装多少水取决于左右两边高于当前位置的较小值\n",
    "更明确地，找出当前位置左边的最大值，以及右边的最大值，再取较小值，即为当前位置能到达的高度\n",
    "正序和倒序遍历一遍，能得到到达i时，左边的最大值和右边的最大值\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = [0] * n, [0] * n\n",
    "        for i,x in enumerate(height):\n",
    "            left[i] = max(left[i-1], x)\n",
    "        right[-1] = height[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right[i] = max(right[i+1], height[i])\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        ans = 0\n",
    "        for i in range(1, n-1):\n",
    "            tmp = min(left[i-1], right[i+1]) - height[i]\n",
    "            # print(i, tmp)\n",
    "            ans += max(tmp, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        # 前、后最小前缀数组\n",
    "        # 桶原理\n",
    "        # 先把height两边的0去掉\n",
    "        \n",
    "        n = len(height)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "            \n",
    "        pre = [0]*n\n",
    "        pre[0] = height[0]\n",
    "        for i in range(1, n):\n",
    "            pre[i] = max(pre[i-1], height[i])\n",
    "        sur = [0]*n\n",
    "        sur[-1] = height[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            sur[i] = max(sur[i+1], height[i])\n",
    "        print(pre, sur)\n",
    "\n",
    "        sum_ = 0\n",
    "        for i in range(n):\n",
    "            sum_ += (min(pre[i], sur[i])*1-height[i])\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        n = len(height)\n",
    "        if n==0:return 0\n",
    "        left,right = [0]*n,[0]*n\n",
    "        left[0],right[-1] = height[0],height[-1]\n",
    "        for i in range(1,n):\n",
    "            left[i] = max(left[i-1],height[i])\n",
    "        for i in range(n-2,-1,-1):\n",
    "            right[i] = max(right[i+1],height[i])\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            tmp = min(left[i],right[i])\n",
    "            if tmp==-1:continue\n",
    "            res+=(tmp-height[i])\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
